{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chap4 Recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:41:50.212552Z",
     "start_time": "2019-07-01T15:41:50.207201Z"
    }
   },
   "outputs": [],
   "source": [
    "from typing import List, TypeVar, Tuple, Any\n",
    "from functools import lru_cache\n",
    "Num = TypeVar('Num', int, float)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reinforcement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-4.1 \n",
    "Describe a recursive algorithm for finding the maximum element in a sequence, S, of n elements. What is your running time and space usage?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T09:21:11.593840Z",
     "start_time": "2019-07-01T09:21:11.579774Z"
    }
   },
   "outputs": [],
   "source": [
    "def max_recursion(nums: List[Num], n: int) -> Num:\n",
    "    if n == 1:\n",
    "        return nums[0]\n",
    "    return max(nums[n-1], n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T09:21:28.921761Z",
     "start_time": "2019-07-01T09:21:28.903320Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_recursion([1, 3, 2, 6, 10], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度为$O(n)$, 因为没有用到额外的空间，所以空间复杂度为$O(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-4.6\n",
    "Describe a recursive function for computing the n th Harmonic number, $H_n = \\sum_{i=1}^{n} \\frac{1}{n}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T09:25:45.166709Z",
     "start_time": "2019-07-01T09:25:45.156759Z"
    }
   },
   "outputs": [],
   "source": [
    "def harmonic_recursion_1(n: int) -> Num:\n",
    "    if n == 1:\n",
    "        return n\n",
    "    return 1/n + harmonic_recursion_1(n-1)\n",
    "\n",
    "# python doesn't support tail-call optimization\n",
    "def harmonic_recursion_2(n: int, acc = 0) -> Num:\n",
    "    if n == 0:\n",
    "        return acc\n",
    "    return harmonic_recursion_2(n-1, acc + 1/n)\n",
    "\n",
    "@lru_cache(maxsize=None)\n",
    "def harmonic_recursion_3(n: int) -> Num:\n",
    "    if n == 1:\n",
    "        return n\n",
    "    return 1/n + harmonic_recursion_1(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第一个是普通版本；第二个是采用了尾递归的写法（但是Python并没有进行尾递归优化）；第三个是采用了内建的`lru_cache`。Benchmerking结果如下：\n",
    "```\n",
    "In [49]: %timeit harmonic_recursion_1(50)                                                                                                                      \n",
    "9.01 µs ± 104 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n",
    "\n",
    "In [50]: %timeit harmonic_recursion_2(50)                                                                                                                      \n",
    "11.3 µs ± 62.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n",
    "\n",
    "In [51]: %timeit harmonic_recursion_3(50)                                                                                                                      \n",
    "111 ns ± 0.657 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n",
    "```\n",
    "\n",
    "前两个差别不大，这里*并没有*搞清楚为什么第三个写法会比较快。因为按照文档所说，这里的cache,应该仅仅在应用DP算法的时候可以作为备查表，但是这里不同的参数值仅仅是调用了一次，所以理应不会有什么优化才对..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-4.7 \n",
    "Describe a recursive function for converting a string of digits into the in-\n",
    "teger it represents. For example, '13531' represents the integer 13, 531."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T09:30:18.288236Z",
     "start_time": "2019-07-01T09:30:18.274795Z"
    }
   },
   "outputs": [],
   "source": [
    "def char_to_int(char: str) -> int:\n",
    "    \"\"\"\n",
    "    convert the single number with str type to number type\n",
    "    \"\"\"\n",
    "    return ord(char) - ord('0')\n",
    "\n",
    "def str_to_int(string: str, n: int) -> int:\n",
    "    if n == 1:\n",
    "        return char_to_int(string[0])\n",
    "    return char_to_int(string[n-1]) * (10 ** (n-1)) \\\n",
    "            + str_to_int(string, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T09:30:42.002551Z",
     "start_time": "2019-07-01T09:30:41.983427Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13531"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str_to_int('13531', 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-4.8 \n",
    "Isabel has an interesting way of summing up the values in a sequence A of\n",
    "n integers, where n is a power of two. She creates a new sequence B of half\n",
    "the size of A and sets B[i] = A[2i] + A[2i + 1], for i = 0, 1, . . . , (n/2) − 1. If\n",
    "B has size 1, then she outputs B[0]. Otherwise, she replaces A with B, and\n",
    "repeats the process. What is the running time of her algorithm?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "solution:\n",
    "\n",
    "首先，不妨设$n = 2^m, m\\in \\mathbb{N^+}$.那么，必须经过$\\log n = m$次操作才能完成。将每次的运算次数加总，\n",
    "$$\\frac{n}{2^1} + \\frac{n}{2^2} + \\cdots + \\frac{n}{2^m} = n \\cdot [1-(\\frac{1}{2})^m]\n",
    "= n \\cdot (1 - \\frac{1}{n}) = n - 1 => O(n)$$\n",
    "其中，\n",
    "$$(\\frac{1}{2})^m = (\\frac{1}{2})^{\\log n} = 2^{- \\log n} = \\frac{1}{n}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Creativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.9\n",
    "Write a short recursive Python function that finds the minimum and max-\n",
    "imum values in a sequence without using any loops."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:41:53.773237Z",
     "start_time": "2019-07-01T15:41:53.754415Z"
    }
   },
   "outputs": [],
   "source": [
    "def my_min(n1: Num, n2: Num) -> Num:\n",
    "    if n1 >= n2:\n",
    "        return n2\n",
    "    else:\n",
    "        return n1\n",
    "\n",
    "def my_max(n1: Num, n2: Num) -> Num:\n",
    "    if n1 >= n2:\n",
    "        return n1\n",
    "    else:\n",
    "        return n2\n",
    "\n",
    "def min_max_num(nums: List[Num], n: int) -> Tuple[Num, Num]:\n",
    "    if n == 1:\n",
    "        return (nums[0], nums[0])\n",
    "    return (\n",
    "            my_min(nums[n-1], min_max_num(nums, n-1)[0]),\n",
    "            my_max(nums[n-1], min_max_num(nums, n-1)[1]),\n",
    "            )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:43:16.969961Z",
     "start_time": "2019-07-01T15:43:16.960688Z"
    }
   },
   "source": [
    "注意这里，我们默认是不适用Python的内建求最值的函数的，不然也太无趣了>.<"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:42:21.379422Z",
     "start_time": "2019-07-01T15:42:21.359888Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 7)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_max_num([1, 3, 2, 4, 7], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.10 \n",
    "Describe a recursive algorithm to compute the integer part of the base-two\n",
    "logarithm of n using only addition and integer division."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:44:06.320511Z",
     "start_time": "2019-07-01T15:44:06.310539Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_log_int(n: Num) -> int:\n",
    "    assert n > 0\n",
    "    if n < 2:\n",
    "        return 0\n",
    "    return 1 + get_log_int(n // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:44:19.550008Z",
     "start_time": "2019-07-01T15:44:19.542937Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 3)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_log_int(16), get_log_int(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.11\n",
    "Describe an efficient recursive function for solving the element unique-\n",
    "ness problem, which runs in time that is at most $O(n^2)$ in the worst case\n",
    "without using sorting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:44:56.190343Z",
     "start_time": "2019-07-01T15:44:56.174108Z"
    }
   },
   "outputs": [],
   "source": [
    "def one_diff_all(element:Any, seq: List[Any], length: int) -> bool:\n",
    "    for i in range(length):\n",
    "        if element == seq[i]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def is_unique(seq: List[Any], n: int) -> bool:\n",
    "    if n == 1:\n",
    "        return True\n",
    "    return is_unique(seq, n-1) and one_diff_all(seq[n-1], seq, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:45:20.629982Z",
     "start_time": "2019-07-01T15:45:20.616485Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_unique([1, 2, 3, 4], 4), is_unique([1, 2, 3, 3, 4], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其实这里的思路还是很简单的，不过这里我们要注意不能创建或者复制太多的列表元素，其会占用很多空间，且复制会加大时间成本。此外，我们在Haskell可以更加清晰地看出算法的逻辑：\n",
    "```Haskell\n",
    "allDifferent :: (Eq a) => [a] -> Bool\n",
    "allDifferent list = case list of\n",
    "    []      -> True\n",
    "    (x:xs)  -> x `notElem` xs && allDifferent xs\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.12\n",
    "Give a recursive algorithm to compute the product of two positive integers,\n",
    "m and n, using only addition and subtraction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:47:45.696771Z",
     "start_time": "2019-07-01T15:47:45.686597Z"
    }
   },
   "outputs": [],
   "source": [
    "def multiply(m: int, n: int) -> int:\n",
    "    if n == 1:\n",
    "        return m\n",
    "    return m + multiply(m, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:47:50.228521Z",
     "start_time": "2019-07-01T15:47:50.222404Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiply(3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.15\n",
    "Write a recursive function that will output all the subsets of a set of n\n",
    "elements (without repeating any subsets)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:48:33.733675Z",
     "start_time": "2019-07-01T15:48:33.716985Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_subsets(s: List[Any], n: int) -> List[Any]:\n",
    "    if n == 0:\n",
    "        return [[]]\n",
    "    return [[s[n-1]] + i for i in get_subsets(s, n-1)] + get_subsets(s, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:49:03.013223Z",
     "start_time": "2019-07-01T15:49:02.999075Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['c', 'b', 'a'], ['c', 'b'], ['c', 'a'], ['c'], ['b', 'a'], ['b'], ['a'], []]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_subsets(['a', 'b', 'c'], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.16\n",
    "Write a short recursive Python function that takes a character string s and\n",
    "outputs its reverse. For example, the reverse of 'pots&pans' would be\n",
    "'snap&stop'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:49:48.207761Z",
     "start_time": "2019-07-01T15:49:48.197219Z"
    }
   },
   "outputs": [],
   "source": [
    "def reverse_str(s: str, n: int) -> str:\n",
    "    if n == 1:\n",
    "        return s[0]\n",
    "    return s[n-1] + reverse_str(s, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:50:08.922380Z",
     "start_time": "2019-07-01T15:50:08.909699Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'snap&stop'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse_str('pots&pans', 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.17\n",
    "Write a short recursive Python function that determines if a string s is a\n",
    "palindrome, that is, it is equal to its reverse. For example, 'racecar' and\n",
    "'gohangasalamiimalasagnahog' are palindromes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:50:57.212175Z",
     "start_time": "2019-07-01T15:50:57.205246Z"
    }
   },
   "outputs": [],
   "source": [
    "def is_palindrome(s: str) -> bool:\n",
    "    def judge(s: str, start: int, end: int) -> bool:\n",
    "        n = end - start + 1\n",
    "        if n <= 1:\n",
    "            return True\n",
    "        return (s[start] == s[end]) and judge(s, start+1, end-1)\n",
    "    return judge(s, 0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:51:21.234680Z",
     "start_time": "2019-07-01T15:51:21.222623Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_palindrome('racecar'), is_palindrome('racecarss')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.18\n",
    "Use recursion to write a Python function for determining if a string s has\n",
    "more vowels than consonants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:51:55.648015Z",
     "start_time": "2019-07-01T15:51:55.638326Z"
    }
   },
   "outputs": [],
   "source": [
    "def count_vowels(s: str, n: int) -> int:\n",
    "    vowels = 'aeiouAEIOU'\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if s[n-1] in vowels:\n",
    "        return 1 + count_vowels(s, n-1)\n",
    "    else:\n",
    "        return count_vowels(s, n-1)\n",
    "\n",
    "def is_more_vowel(s: str) -> bool:\n",
    "    num_vowel = count_vowels(s, len(s))\n",
    "    num_consonants = len(s) - num_vowel\n",
    "    if num_vowel > num_consonants:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:52:05.163970Z",
     "start_time": "2019-07-01T15:52:05.157753Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_more_vowel('hello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.19\n",
    "Write a short recursive Python function that rearranges a sequence of integer values so that all the even values appear before all the odd values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:52:40.418402Z",
     "start_time": "2019-07-01T15:52:40.411899Z"
    }
   },
   "outputs": [],
   "source": [
    "def even_before_odd(nums: List[int]) -> List[int]:\n",
    "    if not nums:\n",
    "        return []\n",
    "    if nums[0] % 2 == 0:\n",
    "        return [nums[0]] + even_before_odd(nums[1:])\n",
    "    else:\n",
    "        return even_before_odd(nums[1:]) + [nums[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:52:49.523025Z",
     "start_time": "2019-07-01T15:52:49.517802Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 3, 1]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "even_before_odd([1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.20\n",
    "Given an unsorted sequence, S, of integers and an integer k, describe a\n",
    "recursive algorithm for rearranging the elements in S so that all elements\n",
    "less than or equal to k come before any elements larger than k. What is\n",
    "the running time of your algorithm on a sequence of n values?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:53:19.926412Z",
     "start_time": "2019-07-01T15:53:19.916814Z"
    }
   },
   "outputs": [],
   "source": [
    "def seperate_by_k(nums: List[int], k: int) -> List[int]:\n",
    "    if not nums:\n",
    "        return []\n",
    "    if nums[0] <= k:\n",
    "        return [nums[0]] + seperate_by_k(nums[1:], k)\n",
    "    else:\n",
    "        return seperate_by_k(nums[1:], k) + [nums[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:53:35.023319Z",
     "start_time": "2019-07-01T15:53:35.009684Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 5, 7]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seperate_by_k([1, 2, 3, 7, 5, 3], 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.21\n",
    "Suppose you are given an n-element sequence, S, containing distinct in-\n",
    "tegers that are listed in increasing order. Given a number k, describe a\n",
    "recursive algorithm to find two integers in S that sum to k, if such a pair\n",
    "exists. What is the running time of your algorithm?\n",
    "\n",
    ">hint:The beginning and the end of a range of indices in S can be used\n",
    "as arguments to your recursive function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:54:38.315900Z",
     "start_time": "2019-07-01T15:54:38.308183Z"
    }
   },
   "outputs": [],
   "source": [
    "def sum_to_k(nums: List[int], k: int, start: int, end: int) -> List[int]:\n",
    "    assert len(nums) > 2\n",
    "    if start == end:\n",
    "        return []\n",
    "    if nums[start] + nums[end] == k:\n",
    "        return [nums[start], nums[end]]\n",
    "    elif nums[start] + nums[end] < k:\n",
    "        return sum_to_k(nums, k, start+1, end)\n",
    "    else:\n",
    "        return sum_to_k(nums, k, start, end-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:54:56.797354Z",
     "start_time": "2019-07-01T15:54:56.790064Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_to_k([1, 2, 3, 4], 5, 0, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-4.22\n",
    "Develop a nonrecursive implementation of the version of power from\n",
    "Code Fragment 4.12 that uses repeated squaring.\n",
    "\n",
    "参考[stackoverflow](https://stackoverflow.com/questions/23079443/c-x-to-the-power-n-using-repeated-squaring-without-recursive-function)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:55:44.094884Z",
     "start_time": "2019-07-01T15:55:44.090679Z"
    }
   },
   "outputs": [],
   "source": [
    "def power(x: int, n: int):\n",
    "    result = 1\n",
    "    while n > 0:\n",
    "        while n & 1 == 0:\n",
    "            n //= 2\n",
    "            result *= result\n",
    "        result *= x\n",
    "        n -= 1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-01T15:55:51.265543Z",
     "start_time": "2019-07-01T15:55:51.259729Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "power(2, 5)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "273.2px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
